글 작성 이유

제가 생각하기에 저는 컴공과를 다니고 있지만 자료구조와 알고리즘에 대한 지식이 체화되지 않아서, 언젠가 한 번 제대로 개념 정리를 하고 가야겠다는 생각을 하고 있었습니다.

그리고 이번에 매일 알고리즘 문제를 한 개씩 풀기 시작하면서, 알고리즘 문제풀이에 필요한 개념을 정리할 필요성을 절실히 느꼈습니다.

그래서 자료구조의 기본중의 기본이라고 할 수 있는 스택과 큐의 개념, 그리고 Java에서 제공하는 Collection을 사용하는 방법을 정리해보려고 합니다.

스택과 큐

스택과 큐는 선형 자료구조에 해당하는 대표적인 자료구조입니다.

스택(Stack)

개념

스택은 나중에 들어간 요소가 가장 먼저 나오는 후입선출(Last In First Out, LIFO) 방식의 자료구조입니다.

입구와 출구가 동일한, 한 쪽이 막힌 통로를 생각하면 쉽습니다.

• 관련 용어
  • top : 스택의 맨 위를 가리키며, 가장 최근에 입력한 데이터가 존재하는 위치입니다.
  • push : top에 데이터를 입력하는(추가하는) 작업을 의미합니다.
  • pop : top에서 데이터를 꺼내는(삭제하는) 작업을 의미합니다.

• 활용 사례
  • DFS(깊이 우선 탐색) 구현

Java에서 사용하기

자바의 java.util 패키지에서 Stack이라는 자료구조 구현체 클래스를 제공하고 있습니다.

public class Stack<E> extends Vector<E> { ... }

Stack이 제공하는 주요 메서드는 다음과 같습니다.

• 사용 예시

  import java.util.Stack;
  
  Stack<String> stack = new Stack<>();
  
  // 요소 추가
  stack.push("Apple");
  stack.push("Banana");
  stack.push("Strawberry");
  stack.push("Grape");
  
  // 스텍의 요소 출력
  log.debug("stack :: " + stack);
  
  // 스택의 요소 제거
  stack.pop();            // "Grape" 요소 제거
  stack.pop();            // "Strawberry" 요소 제거
  
  // 스텍의 요소 출력
  log.debug("stack :: " + stack); // [Apple, Banana]

  예시 코드 출처: Contributor9:티스토리

큐(Queue)

개념

큐는 처음 들어간 요소가 가장 먼저 나오는 선입선출(First In First Out, FIFO) 방식의 자료구조입니다.

입구와 출구가 양 끝에 따로 존재하는 통로를 생각하면 쉽습니다.

• 관련 용어
  • front : 큐의 출구에 해당하며, 처음 입력한 데이터가 존재하는 위치입니다.
  • rear : 큐의 입구에 해당하며, 마지막으로 입력한 데이터가 존재하는 위치입니다.
  • enqueue : rear에 새로운 데이터를 삽입하는 작업을 의미합니다.
  • dequeue : front에서 데이터를 꺼내는 작업을 의미합니다.

• 활용 사례
  • BFS(너비 우선 탐색) 구현

Java에서 사용하기

자바의 java.util 패키지에서 Queue라는 자료구조 인터페이스를 제공하고 있습니다.

public interface Queue<E> extends Collection<E> { ... }

Queue가 제공하는 주요 메서드는 다음과 같습니다.

• 사용 예시

  import java.util.LinkedList;
  import java.util.Queue;
  
  Queue<String> queue = new LinkedList<>();
  
  // 큐의 요소를 넣어줍니다.
  queue.offer("Apple");
  queue.offer("Banana");
  queue.offer("Strawberry");
  queue.offer("Grape");
  
  // 큐의 값을 출력합니다.
  log.debug("queue :: " + queue);
  
  // 큐의 첫번째 요소를 제거합니다.(Apple 제거)
  queue.poll();
  
  // 큐의 값을 출력합니다.
  log.debug("queue :: " + queue);     // ["Banana", "Strawberry", "Grape"]

  예시 코드 출처: Contributor9:티스토리